'''
https://leetcode.cn/problems/split-array-largest-sum/
'''

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def helper(limit):
            # 每一个子数组累加和不超过limit，可以划分多少个子数组
            cur_sum, ans = 0, 0
            for num in nums:
                if num > limit:
                    return float('inf')
                if cur_sum + num > limit:
                    ans += 1
                    cur_sum = num
                else:
                    cur_sum += num
            return ans + 1

        l, r = 0, sum(nums)
        ans = 0
        while l <= r:
            limit = (l + r) // 2
            if helper(limit) <= k:
                ans = limit
                r = limit - 1
            else:
                l = limit + 1
        return ans


